package test;

import java.util.Arrays;
import java.util.HashMap;
/**
 * @Date 2020/04/18
 * @author 王光浩  
 * @Thining 先排序，然后利用HashMap获取天数
 */
public class MyMethodTwo {
	public int[] getTriggerTime(int[][] increase, int[][] requirements) {
		int[][] ReC = new int[requirements.length][2];
		int[][] ReR = new int[requirements.length][2];
		int[][] ReH = new int[requirements.length][2];
		int lenReq = requirements.length;
		for(int i=0 ; i<lenReq ; i++) {
			ReC[i][0] = requirements[i][0];
			ReC[i][1] = i;
			ReR[i][0] = requirements[i][1];
			ReR[i][1] = i;
			ReH[i][0] = requirements[i][2];
			ReH[i][1] = i;
		}
		//按照升序进行排序
		sort(0,lenReq-1,ReC);
		sort(0,lenReq-1,ReR);
		sort(0,lenReq-1,ReH);
		//获取剧情触发时间
		int lenIncres = increase.length;
		int[] ret = new int[lenReq];
		Arrays.fill(ret, -1);
		//存放三个资源
		int C = 0;
		int R = 0;
		int H = 0;
		int[] index = new int[3];
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); //记录合格的资源
		for(int i=0 ; i<=lenIncres ; i++) {
			if( i!=0 ) {
				C += increase[i-1][0];
				R += increase[i-1][1];
				H += increase[i-1][2];
			}
			//将所有达标的 C 资源下标放入 HashMap中
			int k = index[0];
			for( ; k<lenReq ; k++) {
				if( ReC[k][0]>C )break;
				map.put( ReC[k][1], map.getOrDefault(ReC[k][1], 0)+1 );
				if( map.get(ReC[k][1])==3 ) ret[ReC[k][1]] = i;
			}
			index[0] = k;
			//将所有达标的 R 资源下标放入 HashMap中
			int z = index[1];
			for( ; z<lenReq ; z++) {
				if( ReR[z][0]>R )break;
				map.put( ReR[z][1], map.getOrDefault(ReR[z][1], 0)+1 );
				if( map.get(ReR[z][1])==3 ) ret[ReR[z][1]] = i;
			}
			index[1] = z;
			//将所有达标的 H 资源下标放入 HashMap中
			int y = index[2];
			for( ; y<lenReq ; y++) {
				if( ReH[y][0]>H )break;
				map.put( ReH[y][1], map.getOrDefault(ReH[y][1], 0)+1 );
				if( map.get(ReH[y][1])==3 ) ret[ReH[y][1]] = i;
			}
			index[2] = y;
		}
		for(int i=0 ; i<lenReq ; i++) {
			if( ret[i]==0 ) ret[i] = -1;
		}
		return ret;
	}
	
	
	private void sort(int l,int r,int[][]target) {
		if(l>=r) return;
		int left = l;
		int right = r;
		int[] temp = target[l];
		while(left<right) {
			while(left<right && target[right][0]>=temp[0]) right--;
			target[left] = target[right];
			while(left<right && target[left][0]<temp[0]) left++;
			target[right] = target[left];
		}
		target[left] = temp;
		sort(l,left-1,target);
		sort(left+1,r,target);
	}
}
